# LeetCode 84、柱状图中的最大矩形
# 一、题目描述
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。
图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。
示例:
输入: [2,1,5,6,2,3]
输出: 10
# 二、题目解析
我们依旧用 四步分析法 来分析一下这道题目。
- 模拟：模拟题目的运行。
- 规律：尝试总结出题目的一般规律和特点。
- 匹配：找到符合这些特点的数据结构与算法。
- 边界：考虑特殊情况。
“
以下的整体设计思路参考于 liweiwei 的题解，liweiwei 是 LeetCode 大佬，欢迎前往关注：https://leetcode-cn.com/u/liweiwei1419/
”
# 模拟
相当于给我们这样一块木板，怎么样去切才能得到一个面积最大的矩形。
矩形的面积由 高 和 宽 决定的，高确定的情况下，宽 的数值越大，矩形面积越大；同样的，宽确定的情况下，高 的数值越大，矩形面积越大。
所以，一个可执行的思路就是依次遍历柱形的高度，求出每个高度下能切出的最大矩形时的宽度是多少。
以本题为例，有 6 种情况，高度是 2、1、5、6、2、3。
84图片版.006
84图片版.007
84图片版.008
84图片版.009
84图片版.010
84图片版.011
# 规律
也就是说，在高度确定的情况下，我们要尽可能的去扩充宽度，怎么扩充呢？
向左和向右延伸，直到碰壁。
按照这样的思路，需要循环嵌套两次去遍历，再对比得出最大的矩形面积，这样的代码很好写，时间复杂度来到了 O(N(2))。
for （遍历高）{
while(遍历宽){
}
}
需要优化。
再重复一次，矩形的面积是由 高 和 宽 共同决定的，遍历高这个操作无法省略，优化的方向在于能不能在 O(1) 的时间里获取到它的最大宽度。
宽度是由什么决定的？
左边第一个比当前柱体小的柱体和右边第一个比当前柱体小的柱体。
所以，我们重新来 模拟 一下整个过程。
# 模拟 2
请看上图，当遍历到高度为 2 时，左边界是确定了的，但右边是什么情况一无所知，被阴影笼罩，无法确定右边界，宽度也就无法确定，那先不管，继续前行，让阴影的面积变小。
也就是说，当出现了第一个比当前柱体高度还小的柱体时，可以确定当前柱体的右边界，以上图为例，左边界和右边界确定下来的宽度为 1，此时，高度为 2 的最大矩形面积是 1 * 2 = 2。
我们以上帝视角来看待这个不规则的矩形，高度为 2 的矩形有很多种。
为了方便区分，我们用下标来表示，即下标为 0 的最大矩形面积为 1 * 2 = 2。
继续往下分析，下标为 1 的最大矩形面积是多少呢？
再次重复一下，矩形的面积是由 高 和 宽 来决定的，高确定了，需要去确定 宽，而宽是由左边界与右边界共同确定的。
此时，下标为 1 的矩形左边界是可以确定下来的，但右边是什么情况一无所知，被阴影笼罩，无法确定右边界，宽度也就无法确定，那先不管，继续前行，让阴影的面积变小。
当来到下标为 2 的位置时，我们先来确定下标 2 位置的左边界，有三个选择，分别是 a、b、c，而我们要选择的边界必须满足左边第一个比当前柱体小的柱体，即 c 的位置，否则如果你选 a 、b 都会使得下标 2 位置的矩形高度变小。
image-20210321150021475
此时，下标为 2 的矩形左边界是可以确定下来的，但右边是什么情况一无所知，被阴影笼罩，无法确定右边界，宽度也就无法确定，那先不管，继续前行，让阴影的面积变小。
同样的，下标 3 位置的左边界确定了，右边界还无法确定，继续前行，让阴影的面积变小。
当来到下标 4 的位置时，它的左边界确定了，右边界还无法确定。
不过，下标 3 的右边界可以确定了，是右边下标为 4 位置的边界，此时，它的高度是 6，宽度是 1。
同样的，下标 2 的右边界可以确定了，是右边下标为 4 位置的边界，此时，它的高度是 5，宽度是 2。
现在，剩下下标为 1、4、5 的边界还没有确定下来，继续前行。
当来到下标为 5 位置的时候，它的左边界和右边界可以确定下来了，此时，它的高度是 3，宽度是 1。
下标为 4 的右边界也可以确定下来，此时，它的高度是 2，宽度是 4。
最后，下标为 1 的右边界也确定下来，此时，它的高度是 1，宽度是 6。
# 匹配
我们遍历的方式是从左到右进行遍历的，而对于右边界的确定分为两种情况，一种是马上就确定了，比如下标为 0 和下标为 5 的位置，另外一种是无法立马确定时先存储下来，遍历到后面才回过头来确定，比如下标 1、2、3、4 的位置，并且只要是遇到了当前柱形的高度比它上一个柱形的高度严格小的时候，一定可以确定它之前的某些柱形的最大宽度，并且确定的柱形宽度的顺序是从右边向左边，比如先确定好下标 3 的右边界才后，才再确定下标 2 的右边界。
很显然，栈 这种数据结构符合要求。
“
栈：先进后出，后进先出
”
# 边界
- 矩形不存在
- 矩形长度为 1
# 三、参考代码
# 1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 柱状图中最大的矩形（LeetCode 84）：https://leetcode.cn/problems/largest-rectangle-in-histogram/
class Solution {
public int largestRectangleArea(int[] heights) {
// 初始化最终结果为0
int res = 0;
// 使用单调栈
Stack<Integer> stack = new Stack<>();
// 将给定的原数组左右各添加一个元素0，方便处理
int[] newHeights = new int[heights.length + 2];
// 左边界为 0
newHeights[0] = 0;
// 右边界边界为 0
newHeights[newHeights.length-1] = 0;
// 其余不变
for (int i = 1; i < heights.length + 1; i++) {
newHeights[i] = heights[i - 1];
}
// 整体思路：
// 对于一个高度，如果能得到向左和向右的边界
// 那么就能对每个高度求一次面积
// 遍历所有高度，即可得出最大面积
// 开始遍历
for (int i = 0; i < newHeights.length; i++) {
// 如果栈不为空且当前考察的元素值小于栈顶元素值，
// 则表示以栈顶元素值为高的矩形面积可以确定
while (!stack.isEmpty() && newHeights[i] < newHeights[stack.peek()]) {
// 弹出栈顶元素
int cur = stack.pop();
// 获取栈顶元素对应的高
int curHeight = newHeights[cur];
// 栈顶元素弹出后，新的栈顶元素就是其左侧边界
int leftIndex = stack.peek();
// 右侧边界是当前考察的索引
int rightIndex = i;
// 计算矩形宽度
int curWidth = rightIndex - leftIndex - 1;
// 计算面积
res = Math.max(res, curWidth * curHeight);
}
// 当前考察索引入栈
stack.push(i);
}
// 返回结果
return res;
}
}
# **2、**C++ 代码
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
// 初始化最终结果为0
int res = 0;
// 使用单调栈
stack<int> stk;
// 将给定的原数组左右各添加一个元素0，方便处理
vector<int> newHeigths(heights.size() + 2);
// 左边界为 0
newHeigths[0] = 0 ;
// 右边界边界为 0
newHeigths[heights.size() - 1] = 0;
// 其余不变
for ( int i = 1 ; i < heights.size() + 1 ; i++) {
newHeigths[i] = heights[i - 1];
}
// 整体思路：
// 对于一个高度，如果能得到向左和向右的边界
// 那么就能对每个高度求一次面积
// 遍历所有高度，即可得出最大面积
// 开始遍历
for (int i = 0 ; i < newHeigths.size() ; i++) {
// 如果栈不为空且当前考察的元素值小于栈顶元素值，
// 则表示以栈顶元素值为高的矩形面积可以确定
while (!stk.empty() && newHeigths[i] < newHeigths[stk.top()]) {
// 弹出栈顶元素
int cur = stk.top();
stk.pop();
// 获取栈顶元素对应的高
int curHeight = newHeigths[cur];
// 栈顶元素弹出后，新的栈顶元素就是其左侧边界
int leftIndex = stk.top();
// 右侧边界是当前考察的索引
int rightIndex = i;
// 计算矩形宽度
int curWidth = rightIndex - leftIndex - 1;
// 计算面积
res = max(res, curHeight * curWidth);
}
// 当前考察索引入栈
stk.push(i);
}
// 返回结果
return res;
}
};
# 3、Python 代码
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
# 初始化最终结果为0
res = 0
# 使用单调栈
stack = list()
# 将给定的原数组左右各添加一个元素0，方便处理
newHeights = [0] * (len(heights) + 2 )
# 左边界为 0
newHeights[0] = 0
# 右边界边界为 0
newHeights[len(newHeights)-1] = 0
# 其余不变
for i in range( 1 ,len(heights) + 1 ) :
newHeights[i] = heights[i - 1]
# 整体思路：
# 对于一个高度，如果能得到向左和向右的边界
# 那么就能对每个高度求一次面积
# 遍历所有高度，即可得出最大面积
# 开始遍历
for i in range(len(newHeights)) :
# 如果栈不为空且当前考察的元素值小于栈顶元素值，
# 则表示以栈顶元素值为高的矩形面积可以确定
while stack and newHeights[i] < newHeights[stack[-1]] :
# 弹出栈顶元素
cur = stack[-1]
stack.pop()
# 获取栈顶元素对应的高
curHeight = newHeights[cur]
# 栈顶元素弹出后，新的栈顶元素就是其左侧边界
leftIndex = stack[-1]
# 右侧边界是当前考察的索引
rightIndex = i
# 计算矩形宽度
curWidth = rightIndex - leftIndex - 1
# 计算面积
res = max(res, curWidth * curHeight)
# 当前考察索引入栈
stack.append(i)
# 返回结果
return res